package 排序;

/**
 * https://leetcode-cn.com/problems/sort-list/submissions/
 */
class 排序链表 {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode curHead1 = head;
        ListNode low = head;
        ListNode fast =  head.next;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            low = low.next;
        }
        ListNode mid = low;
        ListNode curHead2 = mid.next;
        mid.next = null;
        ListNode left = sortList(curHead1);
        ListNode right = sortList(curHead2);

        ListNode newHead = new ListNode();
        ListNode newCurHead = newHead;
        while (left != null  && right != null){
            if (left.val < right.val){
                newCurHead.next = left;
                left = left.next;
            }else {
                newCurHead.next = right;
                right = right.next;
            }
            newCurHead = newCurHead.next;
            //这部很重要，每次操作后相应的节点要进行后移
        }
        //这层while走完说明左边链表或者右边链表有一个空了，经过判断把另外一个放进去就好了
        newCurHead.next = left != null ? left : right;//判断那个不是空把它传进去
        //同下面理是要进行拼接操作，把他放在下一个节点
        return newHead.next;//newHead是新建节点，他的每个值都添加在下一个元素，每个返回下一个
    }
}
